\(n\) num de alternativas \(m\) num de votantes

Las métricas:

Dos problemas diferentes:

  1. Tengo datos para todos los valores de \(n\) y \(m\) que quiero predecir luego con el modelo. Hago el modelo con eso y acoto el tiempo de ejecución del algoritmo “en producción”
  2. Lo que necesito para los experimentos: poder saber con qué tipos de perfil va a funcionar cuando incremento el valor de \(n\)

Datos

Exploración de cómo se comportan las métricas. Usando \(n = 8\) y \(n = 9\) y \(m \in \{10,11,20,21,30,31,50,51,80,81,130,131,210,211,340,341,550,551,890,891\}\) genero para posible de \((n, m)\)

Es decir, 2000 perfiles para cada par \((n, m)\) (controlando que NO sean Condorcet). Esto hace un total de 40000 perfiles para cada valor de \(n\).

En los siguientes gráficos (primero para \(n=8\) y después para \(n=9\)) se ve para cada distribución (filas) y valor de \(m\) (columnas) un punto por cada perfil indicando el tiempo de ejecución. Se observa una tendencia a la reducción según aumenta el num de votantes \(m\). Los colores son para resaltar los valores de \(m\) pares e impares. En el primero hay más outliers para números de \(m\) pares, lo cual podría ser debido a los empates de \((o_{ij},o_{ji})\).

Average kemeny distance

Esta métrica es \(\mu_1\). Os mando otro PDF adjunto razonando de dónde sale.

Ejemplo en R

por <- parse_profile_of_rankings("
3, b > d > a > c,
5, c > a > d > b,
2, a > c > b > d
")
v <- votrix(por) # outranking matrix
m <- v[1,2]+v[2,1] # num de votantes
print(v)
##   a b c d
## a 0 7 5 7
## b 3 0 3 5
## c 5 7 0 7
## d 3 5 3 0
v <- v * t(v) # para multiplicar cada par con su simetrico
print(v)
##    a  b  c  d
## a  0 21 25 21
## b 21  0 21 25
## c 25 21  0 21
## d 21 25 21  0
print(sum(v[upper.tri(v)])) # quedarme con la mitad y sumarlo
## [1] 134
print(2*sum(v[upper.tri(v)])/(m*(m-1))) # dividir la suma entre el num triangular
## [1] 2.977778

En los siguientes gráficos muestro para cada valor de \(m\) (filas) el tiempo de ejecución (eje \(y\)) en relación con el valor de \(\mu_1\) del perfil. Cuanto más se incrementa \(\mu_1\), más distancia hay entre los rankings del perfil. Esto se puede interpretar como que menos acuerdo hay entre los votantes y más difícil es llegar a un consenso.

Se ve que hacia la derecha todas acumulan más, la que tiene esto más pronunciado es \(m=11\). Esto tiene sentido ya que los tiempos con \(m\) más pequeñas veíamos que eran más altos. Además, parece lógico que a la derecha haya puntos con tiempo más alto, ya que los rankings del perfil están más distantes y parece lógico que tarde más en resolverse.

También se observa que para valores más pequeños de \(m\) el indice \(\mu_1\) tiende a alcanzar valores más altos. En estos casos hay menos rankings, puede ser que coincida que son más extremos, y que al incrementar el valor de \(m\) el número de rankings sea mayor y tienda a haber más posturas intermedias.

## Para n=8

## Para n=9

Liberando las escala del eje \(y\) se ve mejor el incremento del tiempo de ejecución según se incrementa \(\mu_1\) en cualquier valor de \(m\).

## Para n=8

## Para n=9

Para 8 el rango es [0,28] y para 9 [0,36]. Sin embargo los valores experimentales se acercan a otros límites superiores.

# por comprobar el rango que sea correcto
kemeny_distance(parse_ranking("a>b>c>d>e>f>g>h>i"), parse_ranking("i>h>g>f>e>d>c>b>a"))
## [1] 36
range(data8$mu1)
## [1]  2.040816 15.222222
range(data9$mu1)
## [1]  2.631579 19.418182

Para normalizarlo hay que utilizar \(T_n\)

Rango de posiciones

Se refiere a las posiciones que toman las alternativas en los diferentes rankings del perfil

El rango de posiciones depende solo del número de alternativas \(n\) y es \([0, n-1]\)

Si el mayor rango es pequeño, se intuye menos incertidumbre Histogramas del mayor rango.

## Para n=8

## Para n=9

Si el menor rango es grande, se intuye más incertidumbre Histogramas del menor rango.

## Para n=8

## Para n=9

Histogramas del rango medio. En este caso el eje x ya no es continuo

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Bounds of the distance

Este valor depende del número de alternativas \(n\) y del valor de \(m\)

En teoría, cogiendo todas las posibles permutaciones del set de \(n\) alternativas, si tenemos un perfil de rankings donde los \(m\) votantes dan el mismo ranking, la distancia del ranking ganador al perfil sería 0 y la distancia del ranking más lejano sería \(T_n \cdot m\).

En perfiles reales el rango no es ese, se ve acotado por los margenes de votos que hay entre las alternativas

Este valor depende de los pares \((o_{ij}, o_{ji})\)

Lower bound: Como mínimo la dist será igual a la suma de los mínimos de todos los pares. Y con alta probabilidad mayor porque coger estos mínimos sin ciclos es altamente improbable.

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Haciendo zoom en cada una de las ms para ver mejor la distribución:

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Upper bound:

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Ahora a ver el rango

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Y haciendo zoom

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Relación con el tiempo de ejecución:

## Para n=8

## Para n=9

y con zoom:

## Para n=8

## Para n=9

Margin of the votes in the alternatives

Los márgenes dependen del número de votantes. El rango de valores que puede tomar un margen es \([0, m]\)

Average margins. Depende solo de \(m\), al ser la media no depende de \(n\). Las líneas indican \(\frac{1}{4}\) y \(\frac{1}{2}\) de los votantes.

Se ve que cuanto más se incrementa la \(m\) más se aleja el margen del cuarto de los votantes.

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

En relación con el tiempo

## Para n=8

## Para n=9

Y haciendo zoom:

## Para n=8

## Para n=9

Ahora Most common margin. Este no sabría como normalizarlo. Depende de \(m\), al ser el más común no depende de \(n\).

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Number of different marings. Este tampoco sé como normalizarlo. Depende de \(m\) pero en este caso tb depende del número de rankings que haya en el perfil. Los valores van a salir muy pequeños al normalizar.

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Based on rowsums

La distancia del ranking ganador que obtengo aplicando Borda (su linear extension) al perfil. Esta distancia se ve afectada por \(n\) y por \(m\)

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Respecto al tiempo, parece que hay más ruido en las pares

## Para n=8

## Para n=9

Omega (fuzzieee) número de filas con alpha positivo. Este solo depende del valor de \(n\) ya que su rango es \([0, n]\)

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=8

## Para n=9

Sd de rowsums. La media no se puede hacer porque es siempre la misma ya que la suma de todos los elementos es constante. Cómo normalizaría esto? Porque depende de \(m\)

## Para n=8
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

## Para n=9
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Based on beta

Esta sección son métricas basadas en los valores de beta de cada fila. el valor de beta es el num de elementos de la fila que es mayor que la mitad

Sd

## Para n=8

## Para n=9

Mean tiene un problema, que en los impares siempre es la misma porque uno de los elementos del par tiene que ser mayor que otro sí o sí y la suma de betas da siempre lo mismo.

## Para n=8

## Para n=9

Median

## Para n=8

## Para n=9

Mean-Median. esto se me ocurrió porque en el ranking de condorcet siempre es 0, pero en verdad hay más casos en los que es 0

## Para n=8

## Para n=9

Ponderación del ranking beta, vuelve a haber el mismo problema con las impares

## Para n=8

## Para n=9

Intransitive alternatives

En un paper de Betzler se refiere a estos como dirty triplets. Son alternativas a,b,c tal que a>b, b>c y c>a. El rango de valors que puede tomar este índice viene determinado por \(n\).

## Para n=8

## Para n=9